A Gaussian signal is a signal whose generation probability follows a normal distribution (also called “Gaussian distribution”), where the normal distribution appears in various scenes in mathematical and engineering fields and thus is an extremely important distribution.
It is assumed that a Gaussian signal as an encoding target here has integer signal values. Additionally, in general, it is assumed that the signal average is zero and the signal values are “iid” (independent and identically distributed).
Many methods for encoding an integer signal are known. For example, Golomb codes are widely used by which a signal which follows an exponential distribution (which may be called “Laplacian distribution” or “geometric distribution”, and is a bilateral exponential distribution unless stated otherwise) can be efficiently encoded without using a table for the encoding or decoding, where the codes can be very easily processed and momentarily decoded. In addition, any large integer input value can be encoded using the Golomb codes.
The code representation of the Golomb codes varies depending on a Golomb code parameter (called “g” here) which has an integer value greater than or equal to 1.
The table in FIG. 20 shows Golomb codes (Golomb code parameter g=1, . . . , 6) corresponding to integer z=0, . . . , 10. The Golomb codes has a relationship for each code parameter g, such that when the value of the integer z (to be encoded) increases by the value of g, the code length increases by 1.
As the increase of the code length is moderated in accordance with the increase in the Golomb code parameter g, a relatively large value of the Golomb code parameter g is suitable for encoding a gentle distribution. In contrast, as the increase of the code length becomes rapid in accordance with the decrease in the Golomb code parameter g, a relatively small value of the Golomb code parameter g is suitable for encoding a steep distribution which converges at zero.
In an image signal, a difference in brightness between pixels which are adjacent temporally or spatially, or an orthogonal transformation coefficient of the brightness value of each pixel is an example of the signal which follows the exponential distribution, and the Golomb codes may be used for encoding such a signal.
On the other hand, Huffman codes use a code table, can be momentarily decoded, and the average amount of code thereof is shortest (i.e., compact codes) among all variable-length codes. Additionally, arithmetic codes can compress a static signal source to a logical limit (which may be superior in comparison with the compact codes) by using a method different from that used by the variable-length codes.
Patent-Document 1 as shown later discloses an invention for vector-quantizing a feature quantity of an image in accordance with a binary search tree using a neural network, and this invention relates to a technique for encoding an image by means of dynamic Huffman codes.
FIG. 21 shows frequency distributions of the normal distribution and the exponential distribution, where the average is 0, and the dispersion is 16. The vertical axis shows the frequency probability, and logarithm is used so as to show both tail parts of each distribution in an easily understandable manner. As shown in FIG. 21, in the vertical logarithm scale, the normal distribution has a parabolic form, and the exponential distribution has a triangular form.
In order to encode such a bilaterally symmetrical integer distribution, each value should be converted into an integer greater than or equal to zero by using, mostly, a method of representing each value using sign (positive/negative) information and absolute value information separately, or a relatively simple conversion as shown below.
When the values before and after the above conversion are respectively indicated by a and b, the conversion is represented as:b=2a−1 when a>0b=−2a when a≦0
In accordance with such a conversion, a=−3, −2, −1, 0, 1, 2, 3 are converted respectively into b=6, 4, 2, 0, 1, 3, 5.
When the Golomb codes are used for encoding a Gaussian signal, the encoding efficiency is considerably degraded in comparison with the Huffman codes and the arithmetic codes. This is an essential problem caused because the signal generation probability assumed for the Golomb codes does not follow a normal distribution, but follows an exponential distribution.
Similar to the Golomb codes, there are many kinds of codes which do not need a code table, and may be Fibonacci codes, Elias codes, or Exp-Golomb codes. However, there are no codes to which an assumption that the signal generation probability follows the normal distribution is applied.
Non-Patent Document 1 (shown later) recites on page 8 that “contrarily to what happens for geometric and double-sided geometric distributions, there is no simple, instantaneous code for the normal distribution”. That is, there are no codes to which an assumption that the signal generation probability follows the normal distribution is applied.
Therefore, if the encoding efficiency is given priority in the encoding of a Gaussian signal, conventionally, Huffman codes or arithmetic codes have been used.
However, this also has the following problems:
(i) The arithmetic codes require a frequency table, which is not required by the Golomb codes, in both the encoder and the decoder.
(ii) The Huffman codes require a code table or a frequency table, which is not required by the Golomb codes, in both the encoder and the decoder.
(iii) It is necessary for both kinds of codes to determine in advance a range in which encoding of every input value cannot be performed without an exception process, that is, to detect an input value range.
(iv) For both kinds of codes, the amount of processing is larger than that of the Golomb codes, where the amount of processing of the arithmetic codes is particularly large.
In addition, Non-Patent Document 2 shown below proposes Hybrid Golomb codes by which a generalized Gaussian signal source can be momentarily decoded. Although it is possible to encode and decode any large integer input value in this case, it requires a complex structure, and targets a distribution which is further steeper than the exponential distribution steeper than the normal distribution.
Additionally, if easiness of the encoding processing is given priority in the encoding of a Gaussian signal, conventionally, as shown in Non-Patent Document 1, the Golomb codes have been used at the cost of the encoding efficiency. However, this case has a problem that optimization of the Golomb code parameter is necessary.
Patent Document 1: Japanese Unexamined Patent Application, First Publication No. 2001-5967
Non-Patent Document 1: P Boldi, S Vigna: “Compressed perfect embedded skip lists for quick inverted-index lookups”, Proceedings of String Processing and Information Retrieval, 12th International Conference, pp. 1-15, 2005
Non-Patent Document 2: S Xue, Y Xu, B Oelmann: “Hybrid Golomb codes for a group of quantised GG sources”, IEE Proceedings, Vision Image and Signal Processing, Vol. 150, No. 4, pp. 256-260, 2003